package 力扣.树.层序遍历;


import java.util.Deque;
import java.util.LinkedList;

public class 层数最深叶子节点的和1302 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);

        TreeNode root21 = new TreeNode(9);
        TreeNode root22 = new TreeNode(20);

        TreeNode root31 = new TreeNode(15);
        TreeNode root32 = new TreeNode(7);

        root.left = root21;
        root.right = root22;
        root22.left = root31;
        root22.right = root32;

        int i = deepestLeavesSum(root);
        System.out.println(i);
    }
    public static int deepestLeavesSum(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        int ans = 0;
        if (root != null){
            deque.offerFirst(root);
        }
        while (deque.size() > 0){
            ans = 0;
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode last = deque.pollLast();
                ans += last.val;
                if (last.left != null){
                    deque.offerFirst(last.left);
                }
                if (last.right != null){
                    deque.offerFirst(last.right);
                }
            }
        }
        return ans;
    }
}
